# -- coding: utf-8 --
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:return [];#如果为空
        lookup = {}#创建map映射
        for d in range(2, 7):
            lookup[str(d)] = [chr(ord('a') + (d - 2) * 3 + i) for i in range(3)]
        # Argh !! for 7,8,9 we cant use the above pattern !!
        lookup["7"] = ["p", "q", "r", "s"]
        lookup["8"] = ["t", "u", "v"]
        lookup["9"] = ["w", "x", "y", "z"]

        xs = [lookup[str(d)] for d in digits]#遍历这个digits里的字符
        #然后取出map里的列表给xs 最后xs就相当于是二维数组

        def backtrack(xs, sols, temp, i, j):
            #i表示当前是digits里的哪一个字符 j表示这个map里的第几个str
            if len(temp) == len(digits):
                sols.append("".join(temp))#把这个string拼接 加入res
            if i < len(xs):
                for j in range(0, len(xs[i])):
                    temp.append(xs[i][j])
                    backtrack(xs, sols, temp, i + 1, j)
                    temp.pop()#回溯

        sols = []
        backtrack(xs, sols, [], 0, 0)
        return sols

    def letterCombinations1(self, digits):
        if not digits: return []
        maps = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        # 构建map
        ret = []
        self.comb(maps, digits, 0, "", ret)
        return ret

    def comb(self, maps, digits, i, path, ret):
        #path做字符串拼接 path并非是引用类型
        if i == len(digits):
            ret.append(path)
            return
        for letter in maps[digits[i]]:
            self.comb(maps, digits, i + 1, path + letter, ret)
        return



s=Solution();
list=s.letterCombinations1('23');
for i in list:
    print(i);